﻿//【初阶】32.红黑树
//【头文件包含】
//C++的主要头文件
#include<iostream>//c++的输入输出流
using namespace std;
#include<string>
#include<vector>
#include<list>
#include<set>
#include<map>
//C的主要头文件
//#include<stdio.h>
//#include<stdlib.h>
//#include<assert.h>
//#include<string.h> 
#include"RBTree.hpp"



//【命名空间】

//【结构体声明】【类声明】
//【函数声明】
void Test1();void Test2();void Test3();


//【主函数】
int main()
{
	Test1();
	Test2();
	Test3();


	cout << "****主函数结束****" << endl;
	return 0;
}

//【函数定义】


/*测试用例*/void Test1()
{
	cout << "****测试用例开始****"<< endl;
	TestRBTree1();
	cout << "****测试用例结束****" << endl << endl;
}

/*测试用例*/void Test2()
{
	cout << "****测试用例开始****" << endl;

	cout << "****测试用例结束****" << endl<<endl;
}

/*测试用例*/void Test3()
{
	cout << "****测试用例开始****" << endl;

	cout << "****测试用例结束****" << endl << endl;
}




//【笔记】
//【初阶】32.红黑树：平衡二叉搜索树
	//AVLTree 
		// 1.插入：a、按搜索树规则插入 b、更新平衡因子 c、更新出现bf=2/-2，则判断需要进行哪种旋转
		// 2.删除：a、按搜索树规则删除 b、更新平衡因子 c、更新出现bf=2/-2，则判断需要进行哪种旋转
		// 左插bf--右插bf++
		// 左删bf++右删bf-- 
		// 插入后当前节点bf=-1/1，高度改变，需要更新父节点
		// 删除后当前节点bf=-1/1, 高度不变，结束
		// 插入后当前节点bf=0，高度不变，不需要更新父节点，结束
		// 插入|删除后父节点=-2/2,根据实际情况对应旋转调整，结束
	//红黑树：近似平衡二叉搜索树
		// 是一种搜索二叉树，每个节点新增一个颜色属性（红色或黑色），树中最长路径不超过最短路径2倍（最短路径全黑、最长路径一黑一红交替） 
		//规则:
			// 1.每个节点不是红色就是黑色
			// 2.根节点是黑色
			// 3.如果一个节点是红色那他的两个子节点就是黑色（没有连续的红节点）
			// 4.每个节点，从该节点到其所有后代节点的简单路径均有相同的黑色
			// 5.每个叶子节点都是黑色（此处叶子节点为空节点）  
	//
	//
	// 








